package top.datacluster.basic.algorithm.leetcode.tree;

import top.datacluster.basic.algorithm.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode199 {

    public List<Integer> rightSideView(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        LinkedList<RootLevel> temp = new LinkedList<>();
        List<Integer> reslut = new ArrayList<>();

        temp.offerLast(new RootLevel(root, 1));
        int level = 0;
        while (temp.size() > 0){
            RootLevel rootLevel = temp.removeFirst();
            if (rootLevel.level > level){
                reslut.add(rootLevel.treeNode.val);
                level++;
            }
            if (rootLevel.treeNode.right != null)
                temp.offerLast(new RootLevel(rootLevel.treeNode.right, rootLevel.level+1));
            if (rootLevel.treeNode.left != null)
                temp.offerLast(new RootLevel(rootLevel.treeNode.left, rootLevel.level+1));
        }
        return reslut;
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        node.left = node1;
        node.right = node2;
        node1.right = node4;
        node2.right = node3;
        new LeetCode199().rightSideView(node);
    }

}

class RootLevel{
    TreeNode treeNode;
    int level;

    public RootLevel(TreeNode treeNode, int level) {
        this.treeNode = treeNode;
        this.level = level;
    }
}



